// m

// 给定两个字符串text1和text2
// 要求返回两个字符串的最长公共子序列的长度，如果不存在公共子序列，则返回0
// 公共子序列：两个字符串所共同拥有的子序列

// 解题思路，动态规划

// 1. 定义状态，定义状态dp[i][j],表示为前i个字符组成的字符串str1与前j个字符组成的字符串str2的最长公共子序列长度为dp[i][j]
// 2. 定义状态转移方程
//  双重循环遍历字符串text1和text2，则状态转移方程为：
//   1. 如果text1[i-1]===text2[j-1],则说明找到了一个公共字符，此时dp[i][j] = dp[i-1][j-1]+1
//   2. 如果text1[i-1] !=text2[j-1],则dp[i][j]需要考虑以下两种情况，取两种情况中最大的那种，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
//      1. text1是前i-1个字符组成的字符串str1与text2前j个字符组成的str2的最长公共子序列长度，即dp[i-1][j]
//      2. text1是前i个字符组成的字符串str1与text2前j-1个字符组成的str2的最长公共子序列长度，即dp[i][j-1]
// 3. 初始化，初始状态下，默认前i个字符组成的字符串str1和前j个字符组成的字符串str2的最长公共子序列长度为0， 即dp[i][j] = 0
// 4. 最终结果，根据状态定义，最后输出dp[size1][size2],其中size1和size2分别为text1和text2的字符串长度

// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2),二维数组保存状态

function longestCommonSubsequence(text1, text2) {
    let size1 = text1.length
    let size2 = text2.length
    let dp = new Array(size1 + 1).fill(0).map(() => new Array(size2 + 1).fill(0))
    for (let i = 1; i <= size1; i++) {
        for (let j = 1; j <= size2; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }
    return dp[size1][size2]
}

let text1 = "abcde", text2 = "ace" 
console.log(longestCommonSubsequence(text1, text2))